Set Operations
A set is an unordered collection of unique values, backed by the same hashing that makes a dict's lookups fast. That's why membership checks and dedup problems reach for a set first: x in some_set runs in O(1) on average, the same as a dict lookup, versus O(n) for scanning a list.
The four operations: | & - ^
O(n + m)Sets support union, intersection, difference, and symmetric difference, either as operators or as named methods that do the exact same thing:
The methods have one advantage the operators don't: they accept any iterable, not just another set, so you can skip building a set out of the other side first:
The operators are stricter in real CPython: both sides have to already be a set, or you get a TypeError. Try it below, though keep in mind the runner on this page is looser about it than a real Python interpreter, so don't be surprised if it doesn't error the same way here:
Note
In CPython, a | [5, 6, 7] raises a TypeError because | only accepts another set on the right side. Either way, the practical takeaway is the same: reach for the method form, a.union(...), whenever the other side might be a list instead of a set, rather than depending on how strict a given Python happens to be about the operator.
Note
Every result above is wrapped in sorted(). A set has no guaranteed order, and printing one directly, uninvolved with any sorting, can print its elements in whatever order the hashing happens to land on. Sort before printing whenever the order you show matters.
Removing duplicates from a list
watch outset(my_list) is the fastest way to dedupe, but it makes no promise about order, so sort before printing if the order shown needs to be predictable:
If the order the values first appeared in matters, dict.fromkeys() dedupes the same way a set does, but a dict remembers insertion order:
Note
The gotcha: don't assume print(some_set) will come out sorted, or in insertion order, or in any order you can rely on. It happens to print in whatever order the elements hash into internally, which can look sorted for small integers and look scrambled for almost anything else. If a problem needs deduping and the original order, reach for dict.fromkeys(), not a plain set.
Common elements between two lists
O(n + m)Turn both lists into sets and intersect them. This finds shared elements in linear time, instead of comparing every element of one list against every element of the other:
unhashable type: 'list'
TypeErrorA set stores elements by their hash, and computing a hash assumes the value never changes. Lists are mutable, so Python won't let one into a set at all:
frozenset is the immutable version of a set, and being immutable makes it hashable, so it can go inside another set or serve as a dict key, two things a regular set can never do:
Note
Only hashable values can live inside a set or serve as a dict key: numbers, strings, tuples of hashable values, and frozensets. Lists, dicts, and plain sets are all mutable, so none of them qualify. If a problem needs a set of groups, or a dict keyed by a group, convert each group to a tuple or frozenset first.
issubset, issuperset, and set comprehensions
issubset(), issuperset(), and the <=/>= operators all check whether one set's elements are entirely contained in another:
Sets support comprehensions the same way lists and dicts do, with {...} instead of [...]:
Where set operations show up in interviews
The single biggest pattern is a seen set: a set that tracks which nodes or cells a traversal has already visited, so it never processes the same one twice.
- Graph Breadth First Search relies on a visited set in essentially every problem in that pattern, to keep the same node from being added to the queue more than once.
- Every DFS problem uses the same idea, whether the visited set is passed explicitly or built into recursion through a set that gets mutated as the traversal goes.
- Beyond traversal, any problem phrased as "find duplicates" or "find elements that appear in both" is almost always faster with a set than with nested loops over lists.